79 单词搜索

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvkwe2/

cost: 28m34s

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<char> curr;
        vector<vector<int>> memo(board.size(), vector<int>(board[0].size(), 0));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0]) {
                    bool ok = this->walk(board, 0, word, memo, i, j);
                    if (ok) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

private:
    bool walk(vector<vector<char>>& board, int k, string& word,
              vector<vector<int>>& memo, int i, int j) {
        if (memo[i][j] == 1) {
            return false;
        }
        if (k == word.size() - 1) {
            return true;
        }
        memo[i][j] = 1;
        if (i > 0 && word[k + 1] == board[i - 1][j]) {
            bool ok = this->walk(board, k + 1, word, memo, i - 1, j);
            if (ok) {
                return true;
            }
        }
        if (j > 0 && word[k + 1] == board[i][j - 1]) {
            bool ok = this->walk(board, k + 1, word, memo, i, j - 1);
            if (ok) {
                return true;
            }
        }
        if (i < board.size() - 1 && word[k + 1] == board[i + 1][j]) {
            bool ok = this->walk(board, k + 1, word, memo, i + 1, j);
            if (ok) {
                return true;
            }
        }
        if (j < board[0].size() - 1 && word[k + 1] == board[i][j + 1]) {
            bool ok = this->walk(board, k + 1, word, memo, i, j + 1);
            if (ok) {
                return true;
            }
        }
        memo[i][j] = 0;
        return false;
    }
};